package com.study.binarysearchtree;

import java.util.ArrayList;
import java.util.Random;

public class Main {

    public static void main(String[] args) {

        /*BST<Integer> bst = new BST<>();

        int[] arr = {5,3,6,8,2,4};

        for (int i = 0; i < arr.length; i++) {
            bst.add(arr[i]);
        }

        /////////////////
        //      5      //
        //   /     \   //
        //  3       6  //
        // / \       \ //
        //2   4       8//
        ////////////////

        System.out.println("------前序遍历----");
        bst.preOrder();
//        System.out.println(bst);
        System.out.println("------前序遍历（非递归实现）----");
        bst.preOrderNR();
        System.out.println("------中序遍历----");
        bst.inOrder();
        System.out.println("------后序遍历----");
        bst.postOrder();
        System.out.println("------层序遍历----");
        bst.levelOrder();*/

        BST<Integer> bst = new BST<>();

        // test removeMin
        for (int i = 0; i < 1000; i++) {
            bst.add(new Random().nextInt(10000));
        }
        ArrayList<Integer> nums = new ArrayList<>();
        while (!bst.isEmpty()) {
            nums.add(bst.removeMin());
        }
        System.out.println(nums);
        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i-1) > nums.get(i))
                throw new IllegalArgumentException("Error.");
        }
        System.out.println("removeMin test completed.");


        // test removeMax
        for (int i = 0; i < 1000; i++) {
            bst.add(new Random().nextInt(10000));
        }
        nums = new ArrayList<>();
        while (!bst.isEmpty()) {
            nums.add(bst.removeMax());
        }
        System.out.println(nums);
        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i-1) < nums.get(i))
                throw new IllegalArgumentException("Error.");
        }
        System.out.println("removeMax test completed.");
    }
}
